package com.sheng.leetcode.year2025.month09.day26;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2025/9/26
 * <p>
 * 611. 有效三角形的个数<p>
 * <p>
 * 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。<p>
 * <p>
 * 示例 1:<p>
 * 输入: nums = [2,2,3,4]<p>
 * 输出: 3<p>
 * 解释:有效的组合是:<p>
 * 2,3,4 (使用第一个 2)<p>
 * 2,3,4 (使用第二个 2)<p>
 * 2,2,3<p>
 * <p>
 * 示例 2:<p>
 * 输入: nums = [4,2,3,4]<p>
 * 输出: 4<p>
 * <p>
 * 提示:<p>
 * 1 <= nums.length <= 1000<p>
 * 0 <= nums[i] <= 1000<p>
 */
public class LeetCode0611 {

    @Test
    public void test() {
//        int[] nums = {2, 2, 3, 4};
//        int[] nums = {4, 2, 3, 4};
        int[] nums = {159, 541, 20, 407, 803, 718, 353, 865, 664, 64, 536, 613, 512, 259, 195, 718, 119, 762, 825, 336, 135, 690, 216, 557, 655, 409, 671, 592, 665, 206, 107, 186, 962, 84, 531, 725, 711, 320, 258, 947, 22, 60, 606, 220, 427, 340, 392, 18, 923, 632, 693, 604, 316, 118, 318, 629, 543, 241, 970, 895, 620, 475, 556, 439, 678, 754, 634, 634, 624, 388, 593, 422, 196, 739, 717, 176, 543, 128, 769, 193, 887, 513, 906, 985, 124, 119, 187, 352, 539, 29, 924, 864, 26, 204, 252, 475, 23, 532, 981, 20, 658, 578, 554, 836, 428, 356, 690, 247, 171, 483, 533, 940, 613, 647, 467, 910, 647, 692, 379, 71, 377, 789, 630, 271, 654, 281, 502, 514, 941, 812, 519, 955, 931, 405, 741, 505, 887, 841, 11, 530, 974, 324, 906, 28, 550, 761, 297, 964, 694, 230, 892, 897, 631, 630, 720, 439, 622, 301, 401, 507, 283, 675, 961, 893, 848, 780, 383, 801, 703, 384, 499, 589, 32, 445, 308, 590, 680, 964, 991, 799, 37, 381, 230, 545, 332, 745, 765, 683, 677, 378, 761, 133, 239, 346, 394, 889, 99, 264, 159, 333, 271, 394, 79, 635, 730, 42, 710, 304, 685, 69, 424, 214, 307, 821, 538, 365, 293, 862, 377, 736, 933, 607, 223, 12, 888, 29, 770, 72, 921, 981, 387, 380, 42, 111, 127, 722, 609, 285, 154, 2, 615, 920, 233, 512, 972, 618, 651, 457, 528, 778, 785, 102, 527, 806, 810, 219, 714, 924, 969, 689, 63, 437, 26, 897, 27, 591, 854, 768, 334, 8, 98, 887, 573, 568, 341, 965, 98, 332, 839, 175, 635, 672, 239, 249, 51, 68, 994, 478, 496, 489, 421, 581, 794, 60, 544, 465, 307, 771, 780, 266, 346, 973, 243, 265, 113, 895, 751, 200, 689, 303, 64, 564, 217, 798, 272, 484, 411, 705, 133, 269, 194, 290, 359, 867, 479, 120, 806, 924, 729, 233, 270, 276, 501, 396, 563, 43, 934, 773, 114, 160, 882, 822, 231, 865, 814, 55, 488, 539, 617, 437, 916, 600, 483, 750, 40, 197, 178, 100, 454, 987, 320, 40, 595, 139, 172, 464, 455, 588, 278, 555, 409, 973, 221, 301, 652, 238, 579, 914, 774, 475, 839, 311, 570, 117, 296, 127, 106, 643, 269, 149, 317, 195, 624, 801, 552, 314, 316, 500, 434, 519, 243, 229, 375, 882, 141, 574, 397, 315, 384, 851, 920, 143, 345, 244, 234, 945, 661, 706, 340, 601, 572, 774, 135, 184, 215, 657, 97, 448, 927, 351, 669, 813, 723, 745, 712, 642, 98, 790, 224, 438, 694, 36, 319, 996, 689, 435, 769, 417, 224, 849, 882, 668, 984, 497, 798, 774, 466, 773, 965, 373, 719, 324, 53, 285, 747, 660, 643, 735, 849, 486, 745, 34, 400, 910, 361, 804, 292, 817, 407, 31, 149, 141, 970, 826, 247, 167, 372, 350, 285, 689, 372, 444, 272, 553, 46, 897, 385, 377, 299, 113, 917, 282, 105, 915, 729, 613, 87, 50, 17, 550, 420, 230, 533, 229, 789, 814, 829, 942, 730, 165, 751, 496, 477, 978, 23, 695, 216, 583, 418, 875, 118, 380, 844, 794, 849, 584, 263, 523, 65, 708, 481, 46, 781, 582, 99, 198, 909, 975, 94, 930, 380, 526, 968, 948, 994, 258, 424, 841, 12, 149, 17, 467, 81, 208, 636, 153, 781, 126, 472, 13, 672, 930, 343, 68, 760, 523, 51, 601, 880, 582, 732, 94, 391, 265, 972, 517, 120, 316, 845, 900, 856, 773, 377, 911, 649, 869, 971, 259, 75, 498, 330, 592, 114, 462, 764, 565, 313, 744, 585, 874, 328, 331, 67, 360, 34, 602, 773, 210, 597, 535, 928, 597, 480, 428, 502, 368, 605, 333, 795, 278, 102, 680, 169, 661, 34, 50, 917, 532, 326, 907, 613, 163, 649, 969, 897, 60, 325, 108, 365, 456, 185, 2, 538, 815, 574, 241, 487, 382, 108, 105, 908, 147, 393, 192, 670, 578, 688, 212, 152, 715, 362, 509, 575, 571, 310, 195, 898, 776, 49, 519, 941, 964, 424, 864, 809, 312, 669, 815, 607, 397, 361, 736, 615, 2, 726, 818, 165, 656, 540, 776, 784, 33, 66, 319, 204, 952, 495, 691, 341, 331, 138, 524, 878, 755, 611, 705, 361, 296, 898, 854, 264, 784, 510, 217, 267, 692, 599, 356, 659, 465, 149, 636, 840, 327, 332, 467, 268, 363, 94, 120, 150, 169, 254, 206, 979, 834, 79, 913, 919, 570, 596, 141, 397, 530, 564, 504, 379, 145, 726, 286, 109, 10, 721, 733, 374, 100, 455, 702, 12, 332, 984, 653, 849, 681, 945, 591, 716, 138, 708, 238, 948, 752, 159, 406, 531, 839, 7, 821, 381, 118, 927, 457, 352, 156, 158, 746, 479, 711, 703, 290, 687, 764, 820, 986, 799, 328, 23, 563, 531, 89, 576, 837, 202, 423, 508, 808, 960, 663, 833, 103, 289, 941, 503, 87, 964, 808, 498, 105, 475, 116, 400, 319, 879, 960, 197, 248, 576, 517, 741, 260, 879, 307, 788, 469, 607, 859, 567, 253, 660, 43, 3, 530, 486, 564, 445, 896, 951, 752, 411, 269, 531, 717, 216, 794, 178, 652, 844, 909, 306, 4, 778, 164, 186, 846, 271, 665, 150, 882, 521, 953, 196, 734, 429, 184, 113, 992, 236, 189, 940, 701, 375, 682, 233, 551, 439, 945, 643, 486, 415, 834, 682, 421, 196, 704, 290, 693, 23, 929, 400, 379, 752, 320, 226, 291, 700, 179, 199, 313, 781, 183, 540, 915, 316, 17, 822, 298, 101, 264, 31, 30, 515, 290, 800, 671, 879, 462, 934, 78, 802, 53, 454, 797, 100, 598, 722, 341, 688, 676, 685, 785, 245, 100, 238, 529, 278, 101, 623, 900, 841, 190, 843, 562, 931, 454, 515, 817, 779, 136, 471, 399, 91, 318, 977, 436, 926, 784, 657, 199, 121, 248, 684, 607, 542, 940, 976, 650, 778, 324, 938, 646, 646, 653, 847};
        System.out.println(new Solution().triangleNumber(nums));
    }
}

class Solution {
    public int triangleNumber(int[] nums) {
        // 要构成三角形，条件是任意两边之和大于第三边即可
        int ans = 0;
        int n = nums.length;
        // 直接循环会导致超时
//        for (int i = 0; i < n; i++) {
//            for (int j = i + 1; j < n; j++) {
//                for (int k = j + 1; k < n; k++) {
//                    if (nums[i] + nums[j] > nums[k]
//                            && nums[i] + nums[k] > nums[j]
//                            && nums[k] + nums[j] > nums[i]) {
//                        ans++;
//                    }
//                }
//            }
//        }
        // 排序后只需要考虑一个条件判断即可
        Arrays.sort(nums);
        for (int k = 2; k < n; k++) {
            int i = 0, j = k - 1;
            while (i < j) {
                // 如果 nums[i] + nums[j] > nums[k]，说明可以组成三角形
                if (nums[i] + nums[j] > nums[k]) {
                    // 所有从 i 到 j 之间的组合都能组成三角形
                    ans += (j - i);
                    j--;
                } else {
                    i++;
                }
            }
        }
        return ans;
    }
}
